This invention relates to decoding codewords in a high speed data transmission system, and more particularly to decoding codewords which have been encoded using a variable-length coding (VLC) scheme.
Variable-length coding is a coding technique often used for lossless data compression. In accordance with this technique, fixed-length data is converted into variable-length codewords according to the statistics of the data. In general, the lengths of the codewords are chosen so that shorter codewords are used to represent the more frequently occurring data and longer codewords are chosen to represent the less frequently occurring data. By properly assigning the variable-length codewords to the library of all possible source codewords, the averaged word length of the variable-length code is shorter than that of the original data and, therefore, data compression is achieved. Huffman code design is a procedure commonly used to construct a minimum redundant variable-length code for a known data statistic. Generally, the encoding process can be implemented by a table-lookup process using the input data to address the table. The codewords and word-lengths are stored as table contents. The code-lengths are used to control interface circuitry to concatenate the variable-length words into a serial bit stream, which is then segmented into fixed-length data segments. The fixed-length data segments are then outputted sequentially, through a buffer, at a constant data rate onto the data channel. At the receiving end, it is difficult to design a decoder to achieve high speed operations. Due to the variable-length nature, each codeword has to be segmented from the received bit string before it can be decoded into a source symbol. This is a recursive operation which cannot be pipelined. Therefore, the design of a high-speed variable-length decoder is always more difficult than the design of a high-speed variable-length encoder.
There are several methods to decode a stream of variable-length codewords. The one most often used is called the tree-searching algorithm. A variable-length code can always be represented by a tree with codewords as leaves (also called terminal nodes). The decoding starts from the root of the code tree and is guided by the received bit string to follow one of two branches at each node. When a leaf is reached, the end of a codeword is detected and it is segmented from the remaining string. This type of decoder includes logic circuitry corresponding to the tree and control circuitry to traverse the code tree. This approach may be slow, especially for long codewords, since a bit-by-bit search through the code tree is required for each decoded symbol. In typical applications, an input symbol is represented by several bits. The speed of shifting received bits into a decoder is several times as high as the averaged speed of decoded data. Moreover, a practical system often needs to be designed to handle the worst-case. Therefore, the tree-searching based decoder has to be operated at the speed of several times of the output data rate.
Such high-speed requirements are particularly critical for the digital transmission of high definition television (HDTV) signals. In such an HDTV system the total sample rate (combining luminance and chrominance signals) is likely 100 MHz. If variable-length coding is used, the maximum length code word could typically be 16 bits. In the worst-case, a bit-by-bit decoder would thus need to shift at 16 times the sample rate, or at 1.6 Gbits/sec, to detect the code words at the sample rate. Such high speeds are very difficult to implement using current IC technology.
Due to the difficulty of implementing high-speed variable-length decoders, there are several special variable-length codes designed for fast and inexpensive decoders. For example, a variable-length encoder with a length-indicating prefix is proposed by J. Cocke et al in U.S. Pat. No. 3,717,851 issued Oct. 24, 1972. In "Variable Word Length Coding for a High Data Rate DPCM Video Coder," Proc. of Picture Coding Symposium, 1986, pp. 54-56, M. E. Lukacs proposed a hardware architecture that is capable of fast decoding of specially designed variable length codes. These approaches tradeoff coding efficiency with hardware speed.
A table-lookup based approach is an alternative to the bit-by-bit search operation. In a table-lookup based approach, such as disclosed in U.S. Pat. No. 3,675,212, issued on Jul. 4, 1972 to J. Raviv et al, the received bit string is compared with the contents of a codeword table. The codeword table has an entry associated with each possible variable-length codeword that includes the decoded fixed-length word and the length of the variable-length word. When the sequence of leading bits in an input register matches one of the entries in the codeword table, a codeword match is indicated. The input register is then shifted by the number of bits indicated by code length entry, thereby making the next sequence of bits available for comparison with entries in the codeword table. Disadvantageously, bit-by-bit shifting at the very high speed multiple of the sample rate is required to enable the decoder to maintain the sample rate of decoding.
In co-pending a patent application, Ser. No. 546,415, filed Jun. 29, 1990, now U.S. Pat. No. 5,173,695 co-invented by the inventor herein, a high-speed variable-length decoder is described which solves many of the problems of the prior art decoders. That decoder includes two cascaded latch circuits, each having a bit capacity equal to the maximum codeword length and which store consecutive bits supplied from an input buffer memory which stores the stream to be decoded in fixed-length data segments; a barrel shifter, which is input from the two latch circuits and which provides a sliding decoding window output equal in length to the maximum codeword length; an accumulator which accumulates, modulo the maximum codeword length, the lengths of the sequentially decoded variable-length codewords; and a table-lookup memory device, which outputs, for an input sequence of bits that begins with the first bit of a variable-length codeword, a fixed-length word corresponding to that variable-length codeword and that variable-length codeword length. As a codeword is decoded during each clock cycle, its length is accumulated and the decoding window of the barrel shifter is shifted to begin with the first bit of the next to-be-decoded codeword. When, during a clock cycle, the accumulated lengths exceeds the maximum codeword length, which indicates that all the bits in the first latch circuit have been decoded, the bits in the second latch are transferred into the first latch and the next fixed-length data-segment of bits is read into the second latch from the buffer memory. With this decoder, a continuous stream of bits from the buffer is always at-the-ready to be decoded and the variable-length codewords can be decoded at the symbol clock rate without the necessity of clocking bits at a very high bit rate.
In the aforedescribed decoder structure, the speed of operation is limited by the operational delay of the components in a critical path that includes the table-lookup memory, the barrel shifter, and the accumulator. It is the accumulator, which is part of its function controls the reading of the fixed-length data segments from the buffer memory into the second latch, that adds a substantial and significant portion of the total operational delay. This delay will have the a deleterious effect for high-speed decoding, such as will be required for HDTV applications.
An object of the present invention is to provide high-speed decoding of variable-length codewords with a structure that has a minimum of delay inducing components in the critical path.